import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 503. 下一个更大元素 II
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 */
public class Solutions_503 {
    public static void main(String[] args) {
        List<int[]> inputs = new ArrayList<>();
        int[] nums1 = {5, 4, 3, 2, 1};  // output: {-1, 5, 5, 5, 5}
        int[] nums2 = {1, 2, 1};  // output: {2, -1, 2}

        inputs.add(nums1);
        inputs.add(nums2);

        for (int[] input : inputs) {
            int[] result = nextGreaterElements(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 解题思路：
     * 既然是循环数组，那么就遍历两次 nums 数组
     * 利用 栈 来记录前面的元素，栈顶元素小于当前元素时，栈顶元素的下一个更大元素就是当前元素
     * 栈中存储的是索引，而不是具体数值
     */
    public static int[] nextGreaterElements(int[] nums) {
        if (nums == null) {
            return new int[0];
        }
        int len = nums.length;
        int[] ans = new int[len];
        Arrays.fill(ans, -1);
        LinkedList<Integer> stack = new LinkedList<>();

        // 遍历两次 nums 数组
        for (int i = 0; i < len * 2; i++) {
            int num = nums[i % len];
            while (!stack.isEmpty() && num > nums[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = num;
            }
            if (i < len) {
                stack.push(i);
            }
        }
        return ans;
    }
}
